﻿/*
 *	Filename: wuyaowei_palindrome.c
 *	 Version: 0.1.0
 *   Description: 回文字符串判断
 *
 *        Author: wuyaowei
 *          Date: 2020-06-13
 *
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Node{
  char data;
  struct Node * next;
}Node;

/*
 *  创建节点
 */
Node * createNode(char val) {
  Node *node = (Node *)malloc(sizeof(Node));
  node->data = val;
  node->next = NULL;
  return node;
}

Node *head = NULL;

/*
 * 使用快慢指针：
 * 1.快指针一次走两步，慢指针走一步；
 * 2.快指针走到尾部时，慢指针在中间，使链表前半部分反转
 * 3.链表后半部分与前半部分的反转比较
 */
int isPalindromeList(Node *head) {
  Node *fast = head;
  Node *slow = head;
  Node *p = slow, *pre = NULL;
  if (NULL == head || NULL == head->next) {
    return -1;
  }

  while(NULL != fast && NULL != fast->next) {
    p = slow;
    slow = slow->next;
    fast = fast->next->next;
    p->next = pre;
    pre = p;
  }

  //如果链表长度为奇数,跳过中间位置
  if (fast != NULL) {
    slow = slow->next;
  }
  

  while(NULL != p && slow != NULL) {
    if (p->data != slow->data) {
      return -1;
    }
    p = p->next;
    slow = slow->next;
  }
  return 1;
}
void main() {
  char str[100];
  printf("输入字符串：\n");
  scanf("%s", str);
  //初始化单链表
  int len = strlen(str);
  Node *p;
  for (int i = 0; i < len; i++) {
       Node *t1 = createNode(str[i]);
       if (i == 0) {
         head = t1;
	 p = t1;
	 continue;
       }
       p->next = t1;
       p = t1;
  }

  int val = isPalindromeList(head);
  if(val == 1) {
    printf("It is palindrome list.\n"); 
  } else {
    printf("It is not palindrome list.\n");
  }
}
